#include <iostream>
using namespace std;
int T;
int M;
int w[105];
int v[105];
int t[105][105];
int ans[105][105];
int f(int num, int capacity_remain){
    cout<<"<"<<num<<" "<<capacity_remain<<">"<<endl;
    if (t[num][capacity_remain]==1)
        return;
    t[num][capacity_remain]=1;
    
    if(num==M-1){
        if(w[num]>capacity_remain) return 0;
        else return v[num];
    }
    else{
        if(w[num]>capacity_remain) return f(num+1, capacity_remain);
        else return max(f(num+1, capacity_remain-w[num])+v[num], f(num+1, capacity_remain));
    }
    
}
int main()
{
    cin>>T;
    cin>>M;
    for(int i=0;i<M;++i){
        cin>>w[i];
        cin>>v[i];
    }
    cout<<f(0,T)<<endl;
    return 0;
}